Given the root of a binary search tree and a target value, return the value in the BST that is closest to the target.
Example 1:
Input: root = [4,2,5,1,3], target = 3.714286 Output: 4
Example 2:
Input: root = [1], target = 4.428571 Output: 1
Constraints:
- The number of nodes in the tree is in the range
[1, 104]. 0 <= Node.val <= 109-109 <= target <= 109
Average Rating: 4.32 (38 votes)
Solution
Approach 1: Recursive Inorder + Linear search, O(N) time
Intuition
The simplest approach (3 lines in Python) is to build inorder traversal
and then find the closest element in a sorted array with built-in
function min.
This approach is simple stupid, and serves to identify the subproblems.
Algorithm
-
Build an inorder traversal array.
-
Find the closest to target element in that array.
Implementation
Complexity Analysis
- Time complexity : O(N) because to build inorder traversal and then to perform linear search takes linear time.
- Space complexity : O(N) to keep inorder traversal.
Approach 2: Iterative Inorder, O(k) time
Intuition
Let's optimise Approach 1 in the case when index k of the closest element is much smaller than the tree heigh H.
First, one could merge both steps by traversing the tree and searching the closest value at the same time.
Second, one could stop just after identifying the closest value, there
is no need to traverse the whole tree.
The closest value is found if the target value is
in-between of two inorder array elements
nums[i] <= target < nums[i + 1]. Then the closest value
is one of these elements.
Algorithm
-
Initiate stack as an empty array and predecessor value as a very small number.
-
While root is not null:
-
To build an inorder traversal iteratively, go left as far as you can and add all nodes on the way into stack.
-
Pop the last element from stack
root = stack.pop(). -
If target is in-between of
predandroot.val, return the closest between these two elements. -
Set predecessor value to be equal to
root.valand go one step right:root = root.right.
-
-
We're here because during the loop one couldn't identify the closest value. That means that the closest value is the last value in the inorder traversal, i.e. current predecessor value. Return it.
Implementation
Complexity Analysis
- Time complexity : O(k) in the average case and O(H+k) in the worst case, where k is an index of closest element. It's known that average case is a balanced tree, in that case stack always contains a few elements, and hence one does 2k operations to go to kth element in inorder traversal (k times to push into stack and then k times to pop out of stack). That results in O(k) time complexity. The worst case is a completely unbalanced tree, then you first push H elements into stack and then pop out k elements, that results in O(H+k) time complexity.
- Space complexity : up to O(H) to keep the stack
in the case of non-balanced tree.
Approach 3: Binary Search, O(H) time
Intuition
Approach 2 works fine when index k of closest element is much smaller than the tree height H.
Let's now consider another limit and optimise Approach 1 in the case of relatively large k, comparable with N.
Then it makes sense to use a binary search: go left if target is smaller than current root value, and go right otherwise. Choose the closest to target value at each step.
Kudos for this solution go to @stefanpochmann.
Implementation
Complexity Analysis
-
Time complexity : O(H) since here one goes from root down to a leaf.
-
Space complexity : O(1).
May 8, 2020 5:07 AM
Can someone explain why approach #3 is O(H)? Wouldn't it be Log N in runtime since we are omitting half the tree each iteration?
August 31, 2020 9:25 PM
For solution #3 , should we return or break when target==root.val. Wont that save the further iterations?
Last Edit: July 16, 2019 11:17 AM
For the first solution, i think it would be better to use buillt in Double.compare method in Java instead of deciding 1, -1
return Double.compare(Math.abs(o1 - target), Math.abs(o2 - target));
or even better using Java 8+
Collections.min(list, Comparator.comparingDouble(o -> Math.abs(o - target)));
This will also take care of returning 0 in case of equal values.
closest = min(root.val, closest, key = lambda x: abs(target - x))
root = root.left if target < root.val else root.right
Interesting way to write it. I thought this was difficult to read (took me a minute to realize it was essentially the same as my solution). Unless there's a code golf competition, I'd rather just write it out fully. Same with the tertiary statements in #1.
cur = root
...
closest = min(abs(target-cur.val), abs(target-closest))
if target < cur.val:
cur = cur.left
else:
cur = cur.right
Hi guys, Why approach #2 's time complexity is O(h) but not O(N) where n indicates the amount of nodes?
I mean if the last TreeNode's value is the closest, the bottom right one, why the time complexity is not O(N) since we have to loop until the last element.
public int closestValue(TreeNode root, double target) {
if (root == null) return -1;
int res = root.val > target ? closestValue(root.left, target): closestValue(root.right, target);
if (res == -1) return root.val;
return Math.abs(root.val - target) > Math.abs(res - target) ? res : root.val;
}April 6, 2020 5:02 AM
If I understand the problem description correctly, shown approach 3 is not correct. we care about te absolute difference between target and tree node values, if we go into left subtree just because target is smaller than the root node, then we might be missing a node in the right subtree that could have much smaller abs difference.
class Solution
{
private Double val = null;
public int closestValue(TreeNode root, double target)
{
if (root == null)
{
return val.intValue();
}
Double currVal = Double.valueOf(root.val);
if (currVal == target)
{
return currVal.intValue();
}
if (val == null || Math.abs(val - target) > Math.abs(currVal - target))
{
val = currVal;
}
return closestValue(currVal > target ? root.left : root.right, target);
}
}
January 25, 2020 11:55 PM
complexity of algo 2 is always O(H) I think. Because with the first traversal loop you always reach a leaf, thus you do around H steps if the tree is balanced
For Approach 3 can't we further elaborate on the time complexity and say that in the case of a balanced tree we will have time complexity O(logN) since O(logN) == O(H) and in unbalanced tree the worst case would be O(N) since the tree's height would equal number of nodes (worst case). Let me know what you think?
You don't have any submissions yet.
xxxxxxxxxx/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */class Solution {public: int closestValue(TreeNode* root, double target) { }};


